package zuosheng.day1;

/**
 * @author lj
 * @Description: 小数和-归并
 * @date 2020-10-31 14:11
 * @QQ 851477108
 */


public class xiaoShuGui {
    public static void main(String[] args){
        int[] arr = {1,3,4,2,5};
        int sum = smallSum(arr);
        System.out.println(sum);
    }

    public static int smallSum(int[] arr){
        if (arr == null || arr.length < 2){
            return 0;
        }

        //放入一个递归函数内，方便求和
        return mergeSort(arr,0,arr.length - 1);

    }
    public static int mergeSort(int[] arr, int l, int r){
        if (l == r){
            return 0;
        }
        int m = l + ((r - l) >> 1);
        //求左边的小数和
        int lSum = mergeSort(arr, l, m);
        //求右边的小数和
        int rSum = mergeSort(arr, m+1, r);
        //求合并时的小数和
        int mSum = merge(arr,l,m,r);
        return lSum + rSum + mSum;
    }

    public static int merge(int[] arr,int l, int m, int r){
        int[] help = new int[r - l + 1];
        int p1 = l;
        int p2 = m+1;
        int i = 0;
        int res = 0;
        while (p1 <= m && p2 <= r){
            // 把都已经排序好的左右部分进行比较
            // 如果是arr[p1]小，那么arr[p2]自己还有后面的数都要大于，所以取出arr[p1]之前，我们比需要将arr[p1]和arr[p2]后面的数全部比较
            // 因为我们已经知道arr[p2]已经排好序,所以只需要把arr[p2]自己和后面的数加起来的总个数就是右边比arr[p1]大的数的个数
            // 右边大于arr[p1]的个数(r - p2 + 1),计算在arr[p1]合并时的小数和(r - p2 + 1) * arr[p1] ，弹出p1,继续p1+1后面过程一致。
            // 如果arr[p2]小，直接默认arr[p2]必小于左边所有的数,弹出。
            res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }

//        while (p1 <= m){
//            help[i++] = arr[p1++];
//        }
//        while (p2 <= r){
//            help[i++] = arr[p2++];
//        }
//        for (i = 0; i < help.length; i++) {
//            arr[l + i] = help[i];
//        }
        return res;
    }
}
